# coding=utf-8
import sys
# class page:
#     def __init__(self, num, time):
#         self.num = num
#         self.time = time

class OPT:
    def __init__(self, memorySize, pageArr):
        self.memorySize = memorySize
        self.pageArr = pageArr
        self.que = ""
        self.pageArrLen = len(self.pageArr)
        self.list = [[-1 for i in range(0, self.pageArrLen)] for j in range(0, self.memorySize)]
        self.pageMissSize = 0
        self.pageMissRate = 0
        self.queue = []
        # 记录遍历到第几个内存块
        self.pos = 1
        self.ci = 0
        self.opt()

    # 页面 num 插入到 list 的指定行 meNum 的列 col 及其后续列中
    def putIn_list(self, num, col, meNum):
        for i in range(col, self.pageArrLen):
            self.list[meNum][i] = num

    def equation(self, col):
        # 当前页面在上一个内存块列表的历史记录 list 中出现则为存在
        for i in range(0, self.memorySize):
            if self.pageArr[col] == self.list[i][col - 1]:
                return True
        return False

    # 计算的是当前页面到所有需要"预测"的内存块中所有的页面 list[0-memsize][col] 在页面 pageArr 中距离最短页面的索引
    def juli(self, num, start):
        for i in range(start, self.pageArrLen):
            if num == self.pageArr[i]:
                return i
        return sys.maxsize

    def opt(self):
        # 第一个必空
        self.putIn_list(self.pageArr[0], 0, 0)
        self.queue.append(self.pageArr[0])

        # 将内存页全部填满
        for i in range(1, self.pageArrLen):
            # 内存放满了
            if self.list[self.memorySize - 1][i - 1] != -1:
                break

            # 如果没放满 ，判断内存中是否有这个数
            if self.equation(i):
                continue
            else:
                # 没有将这个数放入到内存中self.pageArr[i]放入list的 第pos行 第i列到最后一列
                # 初始化 pos = 1
                self.putIn_list(self.pageArr[i], i, self.pos)
                self.queue.append(self.pageArr[i])
                self.pos += 1
                self.ci += 1

        # 循环从pos开始，接着上面放满之后的继续放，将每个页面数组内容放入内存
        for i in range(self.pos, self.pageArrLen):
            # 判断第i个元素是否已经在内存中
            if self.equation(i):
                continue
            else:
                # 不在记录最大值
                Max = 0
                # 记录最大值的坐标
                MaxPos = 0
                """计算的是当前页面到所有需要"预测"的内存块中所有的页面list[0 - memsize][col]在页面 pageArr 中距离最短页面的索引"""
                for row in range(0, self.memorySize):
                    temp = self.juli(self.list[row][i - 1], i)
                    # 判断这个元素是否是最远的
                    if temp > Max:
                        Max = temp
                        MaxPos = row
                # 将最远的元素替换到内存中相应位置 即 MaxPos 行的第 i 列到最后一列全部赋值为当前页面 self.pageArr[i]
                self.putIn_list(self.pageArr[i], i, MaxPos)
                self.queue.append(self.pageArr[i])
                self.ci += 1

        # 输出结果---------------------------------------------------------------------------start
        for i in range(0, self.ci + 1):
            self.que += "%d " % (self.queue[i])
        self.res = ""
        self.res = self.res + "|------"
        for j in range(0, self.pageArrLen - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"

        for j in range(0, self.pageArrLen):
            self.res = self.res + "|%5d" % (self.pageArr[j]) + " "
        self.res = self.res + '|\n'
        self.res = self.res + "|------"
        for j in range(0, self.pageArrLen - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"
        for j in range(0, self.memorySize):
            for i in range(0, self.pageArrLen):
                if self.list[j][i] == -1:
                    self.res = self.res + "|%5c" % (32) + " "
                else:
                    self.res = self.res + "|%5d" % (self.list[j][i]) + " "
            self.res = self.res + "|\n"

        self.res = self.res + "|------"
        for j in range(0, self.pageArrLen - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"

    def get_que(self):
        return self.que

    def get_res(self):
        return self.res

    def get_lv(self):
        return self.ci / self.pageArrLen

    def get_ci(self):
        return self.ci


# 主函数
if __name__ == "__main__":
    OPT(3, [1, 2, 3, 4, 1, 5, 2, 3, 1, 8, 9])
